package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * back
 * 785. 判断二分图
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/1 15:10
 */
public class IsBipartite {

    public static void main(String[] args) {
        IsBipartite test = new IsBipartite();

        // false
        int[][] graph = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};

        // true
//        int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};

        boolean bipartite = test.isBipartite(graph);
        System.out.println(bipartite);
    }

    private int[][] graph;
    private int[] flags;

    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        int length = graph.length;
        this.flags = new int[length];
        Arrays.fill(flags, -1);
        for (int i = 0; i < length; i++) {
            if (flags[i] == -1 && find(i, 0)) {
                return false;
            }
        }
        return true;
    }

    private boolean find(int index, int v) {
        if (flags[index] != -1) {
            return flags[index] != v;
        }
        flags[index] = v;
        int[] ints = graph[index];
        int n = v ^ 1;
        for (int anInt : ints) {
            if (find(anInt, n)) {
                return true;
            }
        }
        return false;
    }

}
